In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
W Bitogrodzie trwają przygotowania do dorocznej Wielkiej Konferencji Bitonicznej. W ramach konferencji odbędzie się prezentacji, które - zgodnie z tradycją - muszą odbywać się dokładnie w tym samym czasie. Wszystkie prezentacje przeprowadzane są w identycznych salach. Każda sala jest w stanie pomieścić co najwyżej uczestników. Liczba sal jest wystarczająca do pomieszczenia wszystkich prezentacji. Jeśli w prezentacji uczestniczy więcej niż słuchaczy, to organizatorzy muszą zarezerwować odpowiednio większą liczbę sal (dokładniej, dla uczestników wymagane jest przygotowanie 1 sal). Organizatorzy konferencji chcą zmaksymalizować swoje zyski - suma uzyskana ze sprzedaży biletów, pomniejszona o koszt wynajęcia sal, powinna być jak największa. Koszt wynajmu każdej z sal jest równy . Bilet wstępu dla jednej osoby na -tą prezentację kosztuje . Ceny biletów zostały tak dobrane, aby na pewno opłacalne było wynajęcie sali dla osób (ale być może opłaca się to również dla mniejszej liczby osób), czyli zysk z wynajęcia jest w takim przypadku nieujemny. Organizatorzy chcą unieważnić niektóre zarezerwowane bilety w celu zmaksymalizowania zysków. Ponieważ Ty pisałeś system rejestracji na konferencję, zatem Tobie przypadło w udziale wykonanie tego zadania.
Napisz program, który:
W pierwszym wierszu wejścia znajdują się cztery liczby całkowite: , , , (, , , ), pooddzielane pojedynczymi odstępami. Liczby te reprezentują odpowiednio: liczbę przeprowadzanych prezentacji, liczbę dokonanych rezerwacji, wielkość każdej z sal oraz koszt wynajęcia jednej sali. Drugi wiersz zawiera dokładnie liczb (), pooddzielanych pojedynczymi odstępami - dolne ograniczenie w tym zapisie wynika z zyskowności wynajęcia sali dla uczestników. Są to ceny biletów na kolejne prezentacje. Kolejne wierszy zawiera opisy dokonanych rezerwacji. Każda rezerwacja reprezentowana jest przez dwie liczby całkowite oraz (, ), oddzielone pojedynczym odstępem. Reprezentują one odpowiednio numer prezentacji, na którą dokonywana jest rezerwacja oraz liczbę rezerwowanych biletów. Dozwolone jest wycofywanie dowolnej liczby zarezerwowanych biletów, a nie tylko pełnych rezerwacji.
Pierwszy i jedyny wiersz wyjścia powinien zawierać dokładnie jedną liczbę całkowitą - maksymalny zysk z konferencji, na jaki mogą liczyć organizatorzy.
3 2 10 30 7 10 8 1 9 3 13poprawną odpowiedzią jest:
83
Dla przykładu powyżej, w celu zmaksymalizowania zysków należy wycofać rezerwację trzech biletów z drugiej rezerwacji.
Autor zadania: Piotr Stańczyk.